/*
 * @lc app=leetcode.cn id=87 lang=typescript
 *
 * [87] 扰乱字符串
 */

// @lc code=start
function isScramble(s1: string, s2: string): boolean {
  /**
   * @description: 判断同长字符串中字符出现次数是否一样
   */
  const hashCode = (s: string): number => {
    let hash = 0;
    for (let c of s) {
      hash += 1 << c.charCodeAt(0);
    }
    return hash;
  };

  /**
   * @description: 记忆化搜索
   */
  const dp = (i: number, j: number, size: number): boolean => {
    if (memo[i][j][size] !== 0) {
      return memo[i][j][size] === 1;
    }

    let str1 = s1.slice(i, size + i);
    let str2 = s2.slice(j, size + j);
    // 两个字串是否相等
    if (str1 === str2) {
      memo[i][j][size] = 1;
      return true;
    }
    // 两个字串的字符是否相同
    // 比如：acdb和abcd是相同的
    if (hashCode(str1) !== hashCode(str2)) {
      memo[i][j][size] = -1;
      return false;
    }
    // 字符串同长并且里面的字符相同但位置不同，可以分割
    for (let k = 1; k < size; k++) {
      if (dp(i, j, k) && dp(i + k, j + k, size - k)) {
        memo[i][j][size] = 1;
        return true;
      }
      if (dp(i, j + size - k, k) && dp(i + k, j, size - k)) {
        memo[i][j][size] = 1;
        return true;
      }
    }

    memo[i][j][size] = -1;
    return false;
  };

  let size = s1.length;
  // 备忘录
  // i：分割s1的起始位置  j:分割s2的起始位置  size:分割的长度
  // memo[i][j][size]表示s1[i,size+i)和s2[j,size+j)字符串是否相同
  let memo = new Array(size)
    .fill(0)
    .map(() => new Array(size).fill(0).map(() => new Array(size + 1).fill(0)));

  return dp(0, 0, s1.length);
}
// @lc code=end
